#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""
"""


class UndirectedGraphNode:
    def __init__(self, x):
        self.label = x
        self.neighbors = []


class Solution:
    '''
    使用了递归
    '''
    def cloneGraph(self, node):
        # 因为图需要联通: undirected图只需要一个节点: 就可以通到其它节点
        self.visited = {}

        return self.clone_rec(node)

    def clone_rec(self, node):
        if not node:
            return node

        label = node.label
        if label in self.visited:
            return self.visited[label]

        # new_node = copy.copy(node)
        # new_node.neighbors = []
        new_node = UndirectedGraphNode(label)
        self.visited[label] = new_node

        for nei in node.neighbors:
            new_nei = self.clone_rec(nei)
            new_node.neighbors.append(new_nei)

        return new_node


def main():
    print("start main")

if __name__ == "__main__":
    main()
